1. Field of the Invention
The present invention relates to Viterbi decoders and Viterbi decoding methods, and more particularly to a Viterbi decoder and a Viterbi decoding method for realizing a simplified circuit configuration.
2. Description of Related Art
In connection with digital data reproducing apparatus such as optical disk drive and magnetic disk drive equipment, a PRML (Partial Response Maximum-Likelihood) which is a combination of partial response and Viterbi decoding methods has been known as a technique for reducing a data error rate, improving reliability, and increasing recording density. Where the PRML is applied to optical disk drive equipment, a PR (1,1) or PR (1,2,1) method providing a low-pass partial response characteristic is employed. The PR (1,2,1) method, which provides a larger degree of attenuation in a high frequency range than the PR (1,1) method, is more suitable for high-density recording.
It has also been known that, in a circuit where NRZI (Non Return to Zero Inverted) recording is performed for modulation codes with minimum run limited to 1 as in the case of RLL (Run Length Limited) (1,7) codes, improvement in data error rate and reduction in circuit scale can be made by arranging a Viterbi decoder which works on a basis of state transition precluding data series violating run limitation, i.e., data series having an inversion time of 1T (`T` represents a clock cycle of one channel).
Referring to FIG. 6, there is shown a trellis diagram of PR (1,2,1) with minimum run limited to 1. In this figure, each state is indicated as a set of channel bit data including the last two bits with respect to the time point of interest (a value of the immediately preceding channel bit and a value of the channel bit further preceding it). In case that there is no run limitation, it is ideal to provide five values for the number of signal levels in equalization to PR (1,2,1). As contrasted, in case that the minimum run is limited to 1, four values {-1, -1/2, 1/2, 1} are provided for the number of ideal reproduction signal levels (reference levels).
In FIG. 6, the arrow mark indicates a direction of state transition. For instance, in case that an original state is 00 (a value of the immediately preceding channel bit and a value of the channel bit further preceding it), if a new channel bit is 1, the reproduction signal level becomes -1/2 and the preceding three channel bits become 001. In state transition, a new state becomes 01 (values of the preceding two channel bits). That is, the current state becomes 01 since the current channel bit is 1 and the preceding channel bit is 0.
In another example that an original state is 10, if a new channel bit is 0, the reproduction signal level becomes -1/2 and the preceding three channel bits become 100. Therefore, a new state becomes 00 (values of the preceding two channel bits).
In a simple combinational situation, there may be 16 (=4.times.4) possible state transitions. In FIG. 6, transitions not marked with an arrow do not take place in PR (1,2,1) with minimum run limitation. In Viterbi decoding, therefore, such transitions are not taken into consideration in principle.
Referring to FIG. 7, there is shown an example of a Viterbi decoder configuration arranged for PR (1,2,1) equalization and reproduction signaling with minimum run limited to 1. A Viterbi decoder evaluates likelihood of every possible data pattern and outputs reproduction data corresponding to a pattern having maximum likelihood. As shown in FIG. 7, the Viterbi decoder basically comprises a branch metric calculating circuit 1, an ACS (add-compare-select) circuit 2, ametric memory 3 andapath memory 4.
The branch metric calculating circuit 1 carries out branch metric calculation for determining the square of a difference between a reproduction signal sample value `y` and each of four ideal levels (reference levels) of PR (1,2,1) signal.
More specifically, the branch metric calculating circuit 1 calculates the square of a difference between the sample value `y` and the reference level -1 ((y-(-1)).sup.2 =(y+1).sup.2), the square of a difference between the sample value `y` and the reference level -1/2 ((y-(-1/2)).sup.2 =(y+1/2).sup.2), the square of a difference between the sample value `y` and the reference level 1/2 ((y-1/2).sup.2), and the square of a difference between the sample value `y` and the reference level 1 ((y-1).sup.2).
The ACS circuit 2 comprises adders 11 to 16, comparators 17 and 18, and selectors 19 and 20. The adder 11 calculates the sum of output data of the branch metric calculating circuit 1 (y+1).sup.2 and path metric data held in register 32 of the metric memory 3, and supplies it to terminals A of the comparator 17 and the selector 19. The adder 12 calculates the sum of output data of the branch metric calculating circuit 1 (y+1/2).sup.2 and path metric data held in register 34 of the metric memory 3, and supplies it to terminals B of the comparator 17 and the selector 19.
The adder 13 calculates the sum of output data of the branch metric calculating circuit 1 (y+1/2).sup.2 and path metric data held in the register 32 of the metric memory 3, and supplies it to a normalizing circuit 31 of the metric memory 3. The adder 14 calculates the sum data of output of the branch metric calculating circuit 1 (y-1/2).sup.2 and path metric data held in register 35 of the metric memory 3, and supplies it to the normalizing circuit 31.
The adder 15 calculates the sum of output data of the branch metric calculating circuit 1 (y-1/2).sup.2 and path metric data held in register 33 of the metric memory 3, and supplies it to terminals A of the comparator 18 and the selector 20. The adder 16 calculates the sum of output data of the branch metric calculating circuit 1 (y-1).sup.2 and path metric data held in the register 35 of the metric memory 3, and supplies it to terminals B of the comparator 18 and the selector 20.
Each of the comparators 17 and 18 compares values input to terminals A and B thereof, and delivers a path select signal 1 or 2, respectively, for letting the selector choose a smaller input value on terminal A or B. According to the path select signal 1, the selector 19 selects a smaller input value on terminal A or B, and outputs it to the normalizing circuit 31. Similarly, according to the path select signal 2, the selector 20 selects a smaller input value on terminal A or B, and outputs it to the normalizing circuit 31.
The normalizing circuit 31 carries out normalization as mentioned below: If each of the registers 32 to 35 continues accumulating input values, an overflow will take place eventually. To prevent this, a certain value is subtracted from values to be supplied to the registers 32 to 35 so that values in the registers 32 to 35 will be within a predetermined value range while maintaining relative magnitude relationship of path metric data.
The path select signals 1 and 2 output from the comparators 17 and 18 of the ACS circuit 2 are fed to memory units 41-1 to 41-n of the path memory 4. The memory unit 41-1 of the path memory 4 comprises selectors 51 and 52 and registers 53 to 56. On the selector 51, terminals A and B thereof receive input `0` from the topmost register 40-1 of the preceding-stage register block 40 and input `0` from the third-level register 40-3. According to the path select signal 1, an input signal at one of the terminals is selected, and output is fed to the register 53. On the selector 52, terminals A and B thereof receive input `1` from the second-level register 40-2 of the register block 40 and input `1` from the bottommost register 40-4. According to the path select signal 2, an input signal at one of the terminals is selected, and output is fed to the register 56. The registers 54 and 55 are supplied with `0` and `1` from the registers 40-1 and 40-4, respectively.
Each of the memory units 41-2 to 41-(n-3) comprises two selectors and four registers as in the memory unit 41-1.
Three memory units 41-(n-2), 41-(n-1), and 41-n in the succeeding stages are arranged in a simpler structure than the preceding memory units.
In the memory unit 41-(n-2), terminals A and B of selector 61 receive input from the topmost register and third-level register of the preceding-stage memory unit 41-(n-3), respectively. According to the path select signal 1, an input signal at one of the terminals is selected, and output is fed to register 63. On selector 62, terminals A and B receive input from the second-level register and bottommost register of the preceding-stage memory unit 41-(n-3), respectively. According to the path select signal 2, an input signal at one of the terminals is selected, and output is fed to register 65. Register 64 is supplied with output of the bottommost register of the memory unit 41-(n-3).
On selector 71 of the memory unit 41-(n-1), terminal A thereof receives input from the register 63 and terminal B thereof receives input from the register 64 of the memory unit 41-(n-2). According to the path select signal 1, the selector 71 selects an input signal at terminal A or B and feeds it to register 72. Register 73 is supplied with output of the register 65.
Selector 76 of the memory unit 41-n selects one of signals input to terminals A and B thereof from the registers 72 and 73 according to the path select signal 1, delivering the output result of Viterbi decoding.
The following will now describe decoding algorithmic operations: A pattern of channel bit data can be expressed as a path in a trellis diagram. An ideal reproduction signal going through this path (i.e., a data pattern having contiguous reference levels) contains noise and distortion in an actual operational application. A degree of closeness between actual and ideal reproduction signals is indicated as a path metric value representing the sum of products of branch metric data.
In case of optical disk digital data, the square of Euclidean distance (sum of squares of differences between reference levels and actual reproduction signal levels at respective time points) is used as a path metric value. In Viterbi decoding, a pattern having maximum likelihood is output as reproduction data, which means a search for a path that provides a minimum path metric value. For path metric determination, it is necessary to calculate each branch metric value, i.e., the square of a difference between reference and actual reproduction signal levels at each point of time. A path metric value can be determined by summing products of branch metric values thus attained.
Since there are four possible states (values of the immediately preceding two channel bits), four possible paths having minimum path metric data exist for respective states.
In contrast, there are six possible transitions to these four states as shown in FIG. 6. That is, the following six transitions are possible: transition through which original state 00 is changed to new state 00 having the latest two channel bit values by receiving new channel bit data 0; transition which original state 10 is changed to new state 00 by receiving new channel bit data 0; transition through which original state 00 is changed to new state 01 by receiving channel bit data 1; transition through which original state 11 is changed to new state 10 by receiving channel bit data 0; transition through which original state 01 is changed to new state 11 by receiving channel bit data 1; and transition through which original state 11 is changed to new state 11 by receiving channel bit data 1.
In the ACS circuit 2, each of the adders 11 to 16 is used to calculate path metric data corresponding to these six state transitions.
More specifically, in transition where original state 00 is changed to new state 00 by receiving channel bit data 0, since the reference signal level is -1, the adder 11 provides a path metric value for new state 00 by adding branch metric data (y-(-1) ).sup.2, supplied from the branch metric calculating circuit 1 based on sample value `y` and reference level -1, and path metric data of original state 00 held in the register 32.
Similarly, in transition where original state 10 is changed to new state 00, the adder 12 provides a path metric value for new state 00 by adding branch metric data (y-(-1/2)).sup.2, supplied from the branch metric calculating circuit 1 based on sample value `y` and reference level -1/2, and path metric data of original state 10 held in the register 34.
In the comparator 17, a path metric magnitude output by the adder 11 for transition from original state 00 to new state 00 is compared with a path metric magnitude output by the adder 12 for transition from original state 10 to new state 00, and the path select signal 1 for selecting a smaller value is fed to the selector 19. As a result, a smaller value of path metric magnitude data corresponding to transition from original state 00 to new state 00 and path metric magnitude data corresponding to transition from original state 10 to new state 00 is selected by the selector 19 and supplied to the normalizing circuit 31.
As shown in FIG. 6, new state 01 is reached only through transition from original state 00. Therefore, the adder 13 provides a new path metric value for new state 01 by adding branch metric data (y-(-1/2)).sup.2, supplied from the branch metric calculating circuit 1 based on sample value `y` and reference level -1/2, and path metric data of original state 00 held in the register 32. Then, the attained path metric value is fed to the normalizing circuit 31.
Also, as shown in FIG. 6, new state 10 is reached only through transition from original state 11. Therefore, the adder 14 provides a path metric value for new state 10 by adding branch metric data (y-1/2).sup.2, supplied from the branch metric calculating circuit 1 based on reference level 1/2, and path metric data of original state 11 held in the register 35. Then, the attained path metric value is fed to the normalizing circuit 31.
New state 11 is reached through two possible transitions from original states 01 and 11. For transition to new state 11, therefore, the processing for selecting a smaller value of path metric magnitude data corresponding to two possible transitions is carried out as in the case of transition to new state 00.
To be more specific, in path metric calculation for transition from original state 01 to new state 11, the adder 15 adds branch metric data (y-1/2).sup.2, supplied by the branch metric calculating circuit 1 based on reference level 1/2, and path metric data of original state 01 held in the register 33. Similarly, in path metric calculation for transition from original state 11 to new state 11, the adder 16 adds branch metric data (y-1).sup.2, supplied from the branch metric calculating circuit 1 based on reference level 1, and path metric data of original state 11 held in the register 35.
In the comparator 18, a path metric magnitude output by the adder 15 for transition from original state 01 to new state 11 is compared with a path metric magnitude for transition from original state 11 to new state 11, and the path select signal 2 is generated for selecting a smaller input value. According to the path select signal 2, the selector 20 selects one of input values from the adders 15 and 16, and feeds it to the normalizing circuit 31 as a path metric value for transition to new state 11.
In the normalizing circuit 31, a predetermined value is subtracted from each of four path metric values corresponding to new states 00, 01, 10 and 11. The resultant value of subtraction is stored into each of the registers 32 to 35 as a path metric value of new state.
The operations mentioned above are repeated in sequence. Each time a new sample value `y` is attained, the path select signal 1 or 2 is generated and a path metric value corresponding to one of states 00 to 11 in each of the registers 32 to 35 is updated and retained.
As shown in FIG. 6, in transition to new state 00, a channel bit generated is 0 regardless of whether original state is 00 or 10. Similarly, in transition to new state 01, 10 or 11, a channel bit generated is 1, 0 or 1, respectively. Therefore, as a channel bit to be provided for transition to each of new states 00, 01, 10 and 11, each of the registers 40-1, 40-2, 40-3 and 40-4 holds 0, 1, 0 or 1 in advance. As shown in FIG. 8, four registers from the topmost level to the bottommost level in each memory unit 41-i are arranged to correspond to paths reaching states 00, 01, 10 and 11, respectively. For each path, channel bit data generated by the first-stage registers 40-1 to 40-4 is transferred to the succeeding stages sequentially according to the path select signal 1 or 2. In this fashion, a channel bit data sequence for each path is generated and retained.
Referring to FIG. 9, there is shown an example of formation of paths S0 to S3 based on data held in four registers in each memory unit 41-i corresponding to states 00, 01, 10 and 11. In this figure, data at the latest time `t` is indicated on the right side, and data at the immediately preceding time `t-1` is indicated on the left side. That is, the right-side memory unit of the path memory 4 in FIG. 7 is indicated on the left side in FIG. 9, and the left-side memory unit of the path memory 4 in FIG. 7 is indicated on the right side in FIG. 9.
In the example shown in FIG. 9, at the time `t-1`, data of path S0 held in the topmost register contains 01100 in chronological order. Similarly, data of paths S1, S2 and S3 held in the second-level to fourth-level registers contain 11001, 01110, and 01111, respectively. Then, at the next time `t`, the following state transitions are assumed to take place; from original state 10 to new state 00, from original state 00 to new state 01, from original state 11 to new state 10, and from original state 11 to new state 11. As mentioned above, in transition to new state 00, 01, 10 or 11, a channel bit generated is 0, 1, 0 or 1 respectively, each being held in each of the registers 40-1, 40-2, 40-3 and 40-4 in advance. In this situation, the immediately preceding channel bit data is transferred to the succeeding-stage registers as described below.
The immediately preceding channel bit data corresponding to states 00 to 11 must be transferred to the registers 53 to 56. As shown in FIG. 6, new state 00 maybe reached from original state 00 or 10. Therefore, a value contained in the register 40-1 corresponding to original state 00 or the register 40-3 corresponding to original state 10 is transferred to the register 53. The path select signal 1 is used to determine which value is to be transferred.
The adder 11 outputs a path metric value corresponding to transition from original state 00 to new state 00, and the adder 12 outputs a path metric value corresponding to transition from original state 10 to new state 00. For instance, if a path metric value corresponding to transition from original state 00 to new state 00 is smaller than that corresponding to transition from original state 10 to new state 00 and it is selected by the selector 19, a probability of transition from original state 00 to new state 00 is higher than that of transition from original state 10 to new state 00. Therefore, in this case, the selector 51 of the memory unit 41-1 selects input at terminal A thereof, and it is held in the register 53. In a case opposite to the above, a path metric value corresponding to transition from original state 10 to new state 00, which is output from the adder 12, is smaller than that corresponding to transition from original state 00 to new state 00, which is output from the adder 12. In this case, a path metric value corresponding to transition from original state 10 to new state 00 is selected by the selector 19 of the ACS circuit 2. Then, for this transition, the selector 51 selects input at terminal B thereof, and it is held in the register 53.
Transition to new state 01 is made from original state 00. Therefore, channel bit data held in the register 40-1 corresponding to original state 00 is supplied to the register 54.
Similarly, since transition to new state 10 is made from original state 11, channel bit data held in the register 40-4 corresponding to original state 11 is supplied to the register 55.
Transition to new state 11 is made from original state 01 or 11. Therefore, channel bit data held in the register 40-2 or 40-4 corresponding to original state 01 or 11 is selected by the selector 52 according to the path select signal 2 and supplied to the register 56.
As mentioned above, the immediately input channel bit data, which is presumed to be correct in path metric judgment, is transferred to and retained in the registers 53 to 56. On issuance of the path select signal 1 or 2, channel bit data held in the memory unit 41-1 is transferred to the succeeding-stage memory unit 41-2. The same operation is also performed in the memory units at further succeeding stages.
In the manner mentioned above, for paths S0 to S3 at the time `t`, (011100), (011001), (011110) and (011111) are provided respectively as shown in FIG. 9.
In FIG. 9, the thick line indicates a path which remains still at a point of time concerned, and the thin line indicates a path which has been discontinued and recognized to be incorrect. In other words, one of the remaining continuous paths in FIG. 9 is selected finally, thereby defining one sequence of data.
In case of PR (1,2,1), data corresponding to 20 to 30 clocks is stored into the path memory 4 to determine one path finally. When one path is determined, values of data sequences S0 to S4 held in four levels of registers are matched mutually.
Therefore, in a memory unit at the final stage or in the vicinity of the final stage in the path memory 4, it is possible to simplify a configuration thereof. In the memory unit 41-(n-2) exemplified in FIG. 7, a value selected by these lector 61 is fed to the register 63, a value selected by the selector 62 is fed to the register 65, and a value output from the bottommost register of the preceding-stage memory unit 41-(n-3) is fed to the register 64. In the memory unit 41-(n-2), the second-level register is eliminated since the relevant data sequence has been defined already.
Further, in the memory unit 41-(n-1), the selector 71 selects output from the register 63 or 64, and a selected value is retained in the register 72. The bottommost register 73 holds a value output from the bottommost register 65 of the preceding stage. In this stage, the topmost register and the third-level register are eliminated.
In the final-stage memory unit 41-n, only the selector 76 is provided, through which output from the register 72 or 73 of the preceding-stage memory unit 41-(n-1) is selected according to the path select signal 1 to deliver final data output.
As described above, in a conventional arrangement of a Viterbi decoder, it is required for the branch metric calculating circuit 1 to perform square operation, resulting in a disadvantage that the circuit scale is considerably large.
Still more, in the conventional Viterbi decoder, the metric memory 3 requires the largest bit width (operation word length), which has a significant effect on a speed of Viterbi decoding operation. This bit width requirement makes it difficult to increase an operation speed of the Viterbi decoder.